from typing import List
from functools import cache  # 导入缓存装饰器


class Solution:
    def minScoreTriangulation(self, v: List[int]) -> int:
        """
        计算凸多边形三角剖分的最小得分
        问题：给定凸多边形的顶点值（按顺序排列），通过连接对角线剖分成n-2个三角形，
              每个三角形得分是其三顶点值乘积，总得分是所有三角形得分之和，求最小总得分

        参数：
            v: 按顺序排列的多边形顶点值列表

        返回：
            三角剖分的最小总得分
        """

        # 缓存装饰器：将已计算的dfs(i,j)结果缓存，避免重复计算，降低时间复杂度
        @cache
        def dfs(i: int, j: int) -> int:
            """
            递归函数：计算从顶点i到顶点j（包含i和j，顶点顺序为i→i+1→...→j）组成的多边形的最小剖分得分

            参数：
                i: 起始顶点索引
                j: 结束顶点索引

            返回：
                该多边形的最小剖分得分
            """
            # 终止条件：如果i和j是相邻顶点（中间没有其他顶点），无法组成三角形，得分0
            if i + 1 == j:
                return 0

            # 核心逻辑：枚举i和j之间的所有顶点k（i < k < j），将多边形i~j剖分为三部分：
            # 1. 三角形(i, k, j) → 得分：v[i] * v[j] * v[k]
            # 2. 多边形(i, k) → 得分：dfs(i, k)
            # 3. 多边形(k, j) → 得分：dfs(k, j)
            # 总得分是三部分之和，取所有可能k中的最小值作为当前多边形的最小得分
            return min(
                dfs(i, k) + dfs(k, j) + v[i] * v[j] * v[k]
                for k in range(i + 1, j)  # k从i+1遍历到j-1，枚举所有可能的中间顶点
            )

        # 整个多边形的顶点范围是从0到len(v)-1，因此返回dfs(0, len(v)-1)
        return dfs(0, len(v) - 1)
